package lecode01;

import java.util.ArrayList;
import java.util.List;

/**
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 规律:
 *  1: 左边的括号数一定大于右边的括号数才可以添加有括号
 *  2： 有括号数等于n时结束添加
 */
public class 括号生成22 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(2));
    }


    public static List<String> generateParenthesis(int n) {
        //结果集
        List<String> res = new ArrayList<>();
        backtracking(n, res, 0, 0, "");
        return res;
    }

    /**
     *
     * @param n      目标数
     * @param lists  相应结果集
     * @param left   左括号数
     * @param right  有括号数
     * @param tag    上一步的结果
     *
     *   其实就是 左边括号 12与右边括号12 的组合
     */
    public static void backtracking(int n, List<String> lists, int left, int right, String tag) {
        //如果左括号数小于有括号数，不成立放弃这一次
        if (right > left) {
            return;
        }
        //如果左右括号=n 添加目标值到结果集 并结束此轮递归
        if (left == n && right == n) {
            lists.add(tag);
            return;
        }
        //先从左边括号开始
        //后从右边括号开始，但是右边括号开始不符合left > right
        if (left < n ){
            backtracking(n, lists, left + 1, right, tag + "(");
        }
        if (right < n ){
            backtracking(n, lists, left, right + 1, tag + ")");
        }
    }
}
